package top.wujinxing.leetcode.bit_operation;

/**
 * @author wujinxing
 * date 2019/4/28 17:43
 * description 字符串数组最大乘积
 *
 * Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
 * Return 16
 * The two words can be "abcw", "xtfn"
 *
 * 题目描述：字符串数组的字符串只含有小写字符。求解字符串数组中两个字符串长度的最大乘积，要求这两个字符串
 * 不能含有相同字符。
 * 本题主要问题是判断两个字符串是否含相同字符，由于字符串只含有小写字符，总共 26 位，因此可以用一个 32 位的
 * 整数来存储每个字符是否出现过
 */
public class MaximumProductOfWordLengths318 {
    public static void main(String[] args) {
        String[] words = {"abcw", "baz", "foo", "bar", "xtfn", "abcdef"};
        System.out.println(maxProduct(words));
    }

    private static int maxProduct(String[] words){
        int n = words.length;
        int[] val = new int[n];
        for (int i=0; i<n; i++){
            for (char c: words[i].toCharArray()){
                val[i] |= 1<<(c-'a');
            }
        }
        int ret = 0;
        for (int i=0; i<n; i++){
            for (int j=i+1; j<n; j++){
                if ((val[i]&val[j])==0){
                    ret = Math.max(ret, words[i].length()*words[j].length());
                }
            }
        }
        return ret;
    }
}
